package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-06-08 19:43
 * @Version 1.0
 **/
public class LastStoneWeightII {

    /**
     * 转换为01背包问题：
     * 这个题目实质上其实就是，将所有的石子分为两堆，求两堆石子的最小绝对值的问题，最理想的答案是两堆石子一样多，但实际上可能会有偏差
     * 假定所有的石子和为sum, 那么最终的一堆石子中必定有一堆的石子总和<=sum/2的，并且我们让其最大化
     * 因此，这个问题就可以转为背包为sum/2的01背包问题, 假定其值为dp[cap]
     * 那么，最终的结果为 sum - 2*dp[cap]
     *
     * 证明：两堆石子的重量分别为x,y
     * 结果为：|x-y|
     * 假设x为其中较小的，那么结果为: y-x  = (x+y)-2*x
     *
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }

        int cap = sum / 2;
        int[] dp = new int[cap +1];
        for (int stone : stones) {
            for (int i = cap; i >= stone; i--) {
                dp[i] = Math.max(dp[i],dp[i-stone]+stone);
            }
        }

        return sum - 2*dp[cap];

    }
}
